#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 4e5 + 5;

int T;
int n, ans, cnt;
int a[N], c[N];
int f[N], pos[N], h[N];
struct node{
    int l, r, k;
}b[N];
bool vis[N], st[N];

int calc() {
    int res = 0, col0 = -1, add0 = -1, col1 = -1, add1 = -1;
    for (int i = 1; i <= n; i ++ ) {
        if (col0 == -1 && c[i] == 0) col0 = i, add0 = a[i];
        else if (col1 == -1 && c[i] == 1) col1 = i, add1 = a[i];
        else if (c[i] == 0) {
            if (add0 == a[i]) res += a[i];
            col0 = i, add0 = a[i];
        } else {
            if (add1 == a[i]) res += a[i];
            col1 = i, add1 = a[i];
        }
    }
    return res;
}

void dfs(int u) {
    if (u == n + 1) {
        ans = max(ans, calc());
        return ;
    }
    c[u] = 0;
    dfs(u + 1);
    c[u] = 1;
    dfs(u + 1);
}

bool cmp(node u, node v) {
    return u.k > v.k;
}

signed main(void) {
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> T;
    while (T -- ) {
        if (n >= 15)
            for (int i = 1; i <= n; i ++ ) pos[i] = 0, f[i] = 0, h[i] = 0, vis[i] = 0, st[i] = 0;
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        ans = 0;
        if (n <= 15) {
           dfs(1);
           cout << ans << '\n';
        } else {
            cnt = 0;
            for (int i = 1; i <= n; i ++ ) {
                if (h[a[i]] == 0) pos[i] = -1;
                else pos[i] = h[a[i]];
                h[a[i]] = i;
            }
            for (int i = 1; i <= n; i ++ )
                if (pos[i] != -1) b[++ cnt] = {pos[i], i, a[i]};
            sort(b + 1, b + cnt + 1, cmp);
            for (int i = 1; i <= cnt; i ++ ) {
                int l = b[i].l, r = b[i].r, k = b[i].k;
                int f = 1;
                for (int j = l + 1; j <= r - 1; j ++ )
                    if (vis[j]) {
                        f = 0;
                        break;
                    }
                if (!f) continue;
                for (int j = l + 1; j <= r - 1; j ++ ) vis[j] = 1;
                st[l] = 1, st[r] = 1;
                ans += k;
            }
            int now = -1;
            for (int i = 1; i <= n; i ++ ) {
                if (st[i]) continue;
                if (now == -1) {
                    now = a[i];
                } else if (now == a[i]) {
                    ans += a[i];
                } else now = a[i];
            }
            cout << ans << '\n';
        }
        
    }
    return 0;
}
